package 简单.位运算;

/**
 * 给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-number-with-alternating-bits/
 */
public class 交替位二进制数_693 {

    public static void main(String[] args) {


        // 1 1 1
        // 0 0 0 1
        for (int i = 0; i < 31; i++) {
            if ((((int) 16 >> i) & 1) == 1) {
                System.out.print(1 + " ");
            } else {
                System.out.print(0 + " ");
            }
        }
        System.out.println(findHighBit(2 * 2 * 2));

    }

    /**
     * 先通过二分查找，找到从左至右第一个的1的bit位
     * 然后遍历记录，前一个位是否和当前位不一样
     *
     * @param n
     * @return
     */
    public boolean hasAlternatingBits(int n) {
        int highBit = findHighBit(n);
        int preBit = (n >> 0) & 1;
        for (int curBit = 1; curBit <= highBit; curBit++) {
            if (preBit == ((n >> curBit) & 1)) {
                return false;
            }
            preBit = (n >> curBit) & 1;
        }
        return true;
    }

    public static int findHighBit(int num) {
        if (num == Integer.MAX_VALUE) {  //正数的最高位最大是31，而位是从0开始的
            return 30;
        }
        int left = 0, right = 29;
        int highBit = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if ((num >> mid) == 1) {
                return mid;
            } else if ((num >> mid) > 1) {
                highBit = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return highBit;
    }

    /**
     * 位运算+脑筋急转弯
     * <p>
     * 1 0 1  向右移一位  0 1 0  进行异或运算  1 1 1
     * 1 0 0  向右移一位  0 1 0  进行异或运算  1 1 0
     * 只有位全是1的数 num&(num+1)==0
     * 1 1 1 -> 7 -> 7+1 -> 0 0 0 1
     *
     * @param n
     * @return
     */
    public boolean hasAlternatingBits2(int n) {
        n = n ^ (n >> 1);
        return (n & (n + 1)) == 0;
    }

}
